#include <ios>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    void mergesort(vector<int>& nums,vector<int>& tmp,int begin,int end,int& ret)
    {
        if(begin>=end)
        {
            return;//分解到了非有效区间
        }
        int mid = (begin+end)/2;
        mergesort(nums,tmp,begin,mid,ret);//继续分解左边部分
        mergesort(nums,tmp,mid+1,end,ret);//分解右边部分
        merge(nums,tmp,begin,mid,end,ret);//合并左边和右边部分
    }
    void merge(vector<int>& nums,vector<int>& tmp,int begin,int mid,int end,int& ret)
    {
        int leftbegin = begin;
        int rightbegin = mid+1;
        int index = 0;
        while(leftbegin<=mid&&rightbegin<=end)
        {
            if(nums[leftbegin]>nums[rightbegin])
            {
                ret+=(mid - leftbegin+1);//这里意味着左边数组后面的数字
                ret%=1000000007;
                //都可以和右边数组的第一个数字组成一个逆序对
                tmp[index++] = nums[rightbegin++];//然后将右边数组中的第一个树放到临时数组中
            }
            else {
                tmp[index++] = nums[leftbegin++];
            }
        }
        while(leftbegin<=mid)
        {
            tmp[index++] = nums[leftbegin++];
        }
        while(rightbegin<=end)
        {
            tmp[index++] = nums[rightbegin++];
        }
        for(int j = 0,i = begin;i<=end;i++)
        {
            nums[i] = tmp[j++];
        }
    }

    int InversePairs(vector<int>& nums) {
       //第二种方法借用归并排序的方法来解决
       int len = nums.size();
       vector<int> tmp(len);
       int ret = 0;
       mergesort(nums,tmp,0,nums.size()-1,ret);
       return ret;
    }
};